package com.tgy.leetcode;

import java.util.ArrayList;
import java.util.List;

/**
 * @Author: tgy
 * @Date: 12/20/20 4:42 PM
 *
 * https://leetcode-cn.com/problems/generate-parentheses/
 */
public class _22_括号生成 {

    public List<String> generateParenthesis(int n) {

        List<String> rets = new ArrayList<>();

        char[] ret = new char[(n << 1)];

        generate(0,rets,ret,n,n);

        return rets;
    }

    private void generate(int level,List<String> rets,char[] ret, int leftNum, int rightNum) {

        if (level == ret.length) {

            rets.add(new String(ret));
            return;
        }


        if ((leftNum  ==  rightNum) || rightNum == 0) {

            ret[level] = '(';
            generate(level+1,rets,ret,leftNum - 1, rightNum);
            return;
        }

        if (leftNum == 0) {

            ret[level] = ')';
            generate(level + 1,rets,ret,0,rightNum - 1);
            return;
        }


        ret[level] = '(';
        generate(level+1,rets,ret,leftNum-1,rightNum);

        ret[level] = ')';
        generate(level + 1,rets,ret,leftNum,rightNum - 1);

    }
}
